1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <cstdlib>
const int maxn = 1e5 + 5;
const double eps = 1e-12;
struct P{
double x, y;
}p[maxn]; int n;
double dis(P a, P b){
return std::sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
P circle(double &r, P A, P B, P C){
double a = (B.x * B.x + B.y * B.y - A.x * A.x - A.y * A.y) / 2;
double b = (C.x * C.x + C.y * C.y - A.x * A.x - A.y * A.y) / 2;
double c = B.x - A.x, d = B.y - A.y;
double e = C.x - A.x, f = C.y - A.y;
P res = (P){(a * f - b * d) / (c * f - e * d), (b * c - a * e) / (c * f - e * d)};
r = dis(res, A);
return res;
}
int main(){
std::scanf("%d", &n);
for (int i = 1; i <= n; i++){
std::scanf("%lf%lf", &p[i].x, &p[i].y);
}
std::random_shuffle(p + 1, p + n + 1);
double r = 0; P O = p[1];
for (int i = 2; i <= n; i++){
if (dis(p[i], O) > r + eps){
O = p[i]; r = 0;
for (int j = 1; j < i; j++){
if (dis(p[j], O) > r + eps){
O = (P){(p[i].x + p[j].x) / 2, (p[i].y + p[j].y) / 2};
r = dis(O, p[j]);
for (int k = 1; k < j; k++)
if (dis(O, p[k]) > r + eps) O = circle(r, p[i], p[j], p[k]);
}
}
}
}
std::printf("%.10lf\n%.10lf %.10lf\n", r, O.x, O.y);
return 0;
}
|